#include "libutil.h"
#include "hash_table.h"
#include "value.h"

#include <stdlib.h>

htable_t* new_htable(int size)
{
  int i;
  htable_t *table = (htable_t*)safe_malloc(sizeof(htable_t));
 
  table->buckets = size;
  table->items = 0;
  table->size = sizeof(value_t*)*size;

  table->array = (value_t**)safe_malloc(table->size);
  
  for(i=0; i<table->buckets; i++)
  {
    table->array[i] = NULL;
  }

  return table;
}


void destroy_htable(htable_t* hash)
{
   int i;
   if(hash == NULL)
     return;
   
   for(i=0; i<hash->buckets; i++)
   {
      free(hash->array[i]);
   }

   free(hash->array);
   free(hash);
}



value_t* htable_find_term(htable_t* hash,char* token)
{
  int i;

  if ( hash == NULL || token == NULL )
    return NULL;
 
  /*check if array is empty*/ 
  if( hash->array == NULL )
    return NULL;
 
  i = hash_str( token, hash->buckets );
  while( hash->array[i] != NULL &&
          strcmp( hash->array[i]->word, token ) != 0)
  {
     i = (i+1) % hash->buckets;
  }
  /*printf("%d\n", i);*/
  return hash->array[i];
 
}


value_t* htable_find_id(htable_t* hash,unsigned int id)
{
  int i;

  if( hash == NULL)
    return NULL;

  /*check if array is empty*/
  if( hash->array == NULL )
    return NULL;


  i = hash_uint( id, hash->buckets );
  while( hash->array[i] != NULL &&
          hash->array[i]->id != id )
  {
     i = (i+1) % hash->buckets;
  }
  
  return hash->array[i];
 
}


void htable_add_term(htable_t* hash,value_t* new)
{
  size_t i;

  if ( hash == NULL || new == NULL ) 
  {
    fprintf(stderr, "add term unsuccessfully!\n");
    exit(-1);
  }

  /*check if array is empty*/
  if( hash->array == NULL )
  {
    fprintf(stderr, "array is not initialized!\n");
    exit(-1);
  }

  /*check if term is empty*/
  if( new->word == NULL )
  {
    fprintf(stderr, "new item is empty!\n");
    exit(-1);
  }

  /*expand hash table */
  if( (hash->items * 2) >= hash->buckets )
  {
     htable_rehash_term( hash );
  }

  i = hash_str( new->word, hash->buckets );

  while( hash->array[i] != NULL &&
         strcmp(hash->array[i]->word, new->word) != 0 )
  {
    i = (i+1) % hash->buckets; 
  }

  if( hash->array[i] == NULL )
  {
     hash->array[i] = new; 
     hash->items++;
  }
  else
     (hash->array[i]->count)++;

}


void htable_add_id(htable_t* hash,value_t* new)
{

  size_t i;

  if ( hash == NULL || new == NULL ) 
  {
    fprintf(stderr, "add term unsuccessfully!\n");
    exit(-1);
  }

  /*check if array is empty*/
  if( hash->array == NULL )
  {
    fprintf(stderr, "array is not initialized!\n");
    exit(-1);
  }

  /*check if term is empty*/
  if( new->word == NULL )
  {
    fprintf(stderr, "new item is empty!\n");
    exit(-1);
  }
  
  /*expand hash table */
  if( (hash->items * 2) >= hash->buckets )
  {
     htable_rehash_id( hash );
  }

  i = hash_uint( new->id, hash->buckets );

  while( hash->array[i] != NULL &&
         strcmp(hash->array[i]->word, new->word) != 0 )
  {
    i = (i+1) % hash->buckets; 
  }

  if( hash->array[i] == NULL )
  {
     hash->array[i] = new; 
     hash->items++;
  }
  else
     (hash->array[i]->count)++;
  
  
}

void htable_rehash_id(htable_t* hash)
{
  htable_t *table; 
  value_t **v;
  int i;

  if ( hash == NULL )
  {
    fprintf(stderr, "rehash_id unsuccessfully\n");
    exit(-1);
  }
  
  if( hash->array == NULL )
  {
    fprintf(stderr, "array is empty!\n");
    exit(-1);
  }

  /*rehash 'hash' and store into 'table'*/
  table = new_htable(hash->items * TIMES);
  v = hash->array;

  for(i=0; i<hash->buckets; i++)
  {
    if( v[i] != NULL )
    {
      htable_add_id(table, v[i]);
    }
  }
  /*****finish to copy*****/
  

  /* copy new table*/
  hash->buckets = table->buckets;
  hash->items = table->items;
  hash->size = table->size;

  /*
  for(i=0; i<hash->buckets; i++)
  {
    free(hash->array[i]); 
  }
  */
  free(hash->array);
  
  hash->array = table->array;
  
  /*free 'table'*/
  free(table);
}

void htable_rehash_term(htable_t* hash)
{ 
  htable_t *table; 
  value_t **v;
  int i;

  if ( hash == NULL )
  {
    fprintf(stderr, "rehash_id unsuccessfully\n");
    exit(-1);
  }
  
  if( hash->array == NULL )
  {
    fprintf(stderr, "array is empty!\n");
    exit(-1);
  }

  /*copy hash to new table*/
  table = new_htable(hash->items * TIMES);
  v = hash->array;

  for(i=0; i<hash->buckets; i++)
  {
    if( v[i] != NULL )
    {
      htable_add_term(table, v[i]);
    }
  }
  /*****finish to copy*****/
  
  
  /* copy new table to hash */
  hash->buckets = table->buckets;
  hash->size = table->size;

  /*
  for(i=0; i<hash->buckets; i++)
  {
    free(hash->array[i]); 
  }
  */
  free(hash->array);

  hash->array = table->array;
  
  /*free 'table'*/
  free(table);
}


value_t** remap_freq_htable(htable_t* htable)
{
  value_t **new_array, **v;
  int i, new_p;
 
  v = htable->array;
  new_array = (value_t**)safe_malloc( htable->size );

  for(i=0; i<htable->buckets; i++)
    new_array[i] = NULL;

  for(i=0, new_p=0; i<htable->buckets; i++)
  {
    if( v[i] != NULL ) 
    {
       new_array[new_p++] = v[i];
       
    }
  }

  insertion_sort( new_array, new_p, cntcmp);
  for(i=0; i<new_p; i++)
  { 
     new_array[i]->id = i;
  }

  return new_array;
}


void dump_htable(htable_t *htable)
{
   int i;
   printf("dump begin...\n");
   for( i=0; i<htable->buckets; i++)
   {
     if( htable->array[i] != NULL )
     { 
       printf("Word: %s\n", htable->array[i]->word);
       printf("Type: %s\n", htable->array[i]->type==0?"word":"non-word");
       printf("Id: %d\n", htable->array[i]->id);
       printf("Count: %d\n", htable->array[i]->count);
       printf("\n");
     }
   }
   printf("\n");
}

/* Paul Hsieh's string hashing function modified to suit my needs.
 * NEVER try to write your own hash function unless you have a
 * few years to waste ...
 * http://www.azillionmonkeys.com/qed/hash.html
 */
size_t
hash_str (char *buf, size_t max)
{
    size_t tmp, result;
    int rem;
    size_t len = strlen (buf);

    result = len;
    if ((len <= 0) || (buf == NULL)) return 0;

    rem = len & 3;
    len >>= 2;
    /* Main loop */
    for (; len > 0; len--) {
        result  += get16bits (buf);
        tmp = (get16bits (buf + 2) << 11) ^ result;
        result = ( result << 16 ) ^ tmp;
        buf += 2 * sizeof (unsigned short);
        result += result >> 11;
    }
    /* Handle end cases */
    switch (rem) {
        case 3: result += get16bits (buf);
                result ^= result << 16;
                result ^= buf[sizeof (unsigned short)] << 18;
                result += result >> 11;
                break;
        case 2: result += get16bits ( buf );
                result ^= result << 11;
                result += result >> 17;
                break;
        case 1: result += *buf;
                result ^= result << 10;
                result += result >> 1;
    }
    /* Force "avalanching" of final 127 bits */
    result ^= result << 3;
    result += result >> 5;
    result ^= result << 4;
    result += result >> 17;
    result ^= result << 25;
    result += result >> 6;

    return  ((result) % (max - 1));
}

/* Thanks to:
** http://www.concentric.net/~Ttwang/tech/inthash.htm */
static size_t
int_hash (unsigned int key)
{
    key += ~(key << 15);
    key ^= (key >> 10);
    key += (key << 3);
    key ^= (key >> 6);
    key += ~(key << 11);
    key ^= (key >> 16);
    return (key);
}

/* A simple throttled integer hashing function. Works pretty
 * well AFAIKT
 */
size_t
hash_uint (unsigned int buf, size_t max)
{
    return (int_hash (buf) % (max - 1));
}

